package com.test.daily.leetcode.y2022.m06.day0610.v05;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/10 下午 11:41
 * @version: 1.0
 */
public class Solution {
    public static int coins(int[] arr, int aim) {
        if (aim == 0) {
            return 0;
        }
        return process(arr, aim, 0);
    }

    public static int process(int[] arr, int rest, int index) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int zhang = 0; rest - arr[index] * zhang >= 0; zhang++) {
            ways += process(arr, rest - zhang * arr[index], index + 1);
        }
        return ways;
    }

    public static int way2(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        for (int index = N; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    ways += dp[index + 1][rest - zhang * arr[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    public static int ways2(int[] arr, int aim) {
        int N = arr.length;
        int dp[][] = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for(int i = N-1; i>=0; i--){
            for(int rest = 0; rest <= aim; rest++){
                dp[i][rest] = dp[i+1][rest];
                if(rest-arr[i] > 0){
                    dp[i][rest] += dp[i][rest-arr[i]];
                }
//                int ways = 0;
//                for(int zhang = 0; zhang*arr[i] <= rest; rest++){
//                    ways += dp[i+1][rest - zhang*arr[i]];
//                }
//                dp[i][rest] = ways;
            }
        }
        return dp[0][aim];
    }
}
